package 哈希表;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 力扣 15
 * @Author zxl
 * @Date 2022/1/17 21:31
 * @Desc 在一个数组中找到三个元素，使其相加等于0（这三个元素就是一个三元组，三个元素不可以重复）、这个数组中可以找到多少组这样的元组
 */
public class 三数之和 {

    public static void main(String[] args) {
        // 输入
        int[] nums = {-1,3,4,-3,0,-1,3,-3};
        // 输出：[[-3,-1,4],[-3,0,3]]
        List<List<Integer>> result = findSumZero(nums);
        System.out.println("结果：" + Arrays.toString(result.toArray()));
    }

    /**
     * 双指针
     * @param nums
     * @return
     */
    public static List<List<Integer>> findSumZero(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {

            if (nums[i] > 0){
                return result;
            }
            // 去重
            if (i >0 && nums[i] == nums[i-1]){
                continue;
            }
            // 初始左右指针
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right){
                if (nums[i]+nums[left] + nums[right] > 0){
                    right --;
                }else if (nums[i]+nums[left] + nums[right] < 0){
                    left ++;
                }else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    // 去重：[0,0,0]
                    while (left < right && nums[right] == nums[right - 1]){
                        right --;
                    }
                    while (left < right && nums[left] == nums[left + 1]){
                        left ++;
                    }
                    left ++;
                    right --;
                }
            }
        }
        return result;
    }
}
